package twobranchTree.levelorder;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/2/20
 * @author 王光浩
 * @Description 给出一颗二叉树，对它进行层序遍历
 * @Thinking 使用队列。
 *           复杂度分析：时间复杂度O（n），空间复杂度O（2n）
 */
public class MyMethodOne {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<List<Integer>>(); //保存最后结果
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        if(root!=null)queue.add(root);
        //进行层序遍历
        while(!queue.isEmpty()) {
        	int size=queue.size();  //当前层的大小
            List<Integer> tem=new ArrayList<Integer>();
            TreeNode node=null;
        	//将当前层的数据加入到tem集合中，并且将下一层的数据加入到队列中
        	while(size!=0) {
        		node=queue.poll();
        		if(node.left!=null)queue.add(node.left);
        		if(node.right!=null)queue.add(node.right);
        		tem.add(node.val);
        		size--;
        	}
        	//将tem集合加入到结果集中
        	result.add(tem);
        }
        return result; 
    }
    
    /**
     * 使用 Queue队列 对二叉树进行层序遍历
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder1(TreeNode root) {
    	List<List<Integer>> ret = new ArrayList<List<Integer>>();
    	Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
    	ArrayList<Integer> level = null;
    	if (root == null)
    		return ret;
    	queue.offer(root);
    	while ( !queue.isEmpty() ) {    		
    		level = new ArrayList<Integer>();
    		TreeNode node = null;
    		for (int i = 0, size = queue.size(); i < size; i ++) {
    			node = queue.poll();
    			level.add(node.val);
    			if (node.left != null) 
    				queue.offer(node.left);
    			if (node.right != null)
    				queue.offer(node.right);
    		}
    	}
    	return ret;
    }
}
